SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>ID3 algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">ID3 algorithm</span></span>

</h1>

</header>

<p>In <a href="Decision_tree_learning" title="Decision tree learning">decision tree learning</a>, <b>ID3</b> (<b>Iterative Dichotomiser 3</b>) is an <a href="Algorithm" title="Algorithm">algorithm</a> invented by <a href="Ross_Quinlan" title="Ross Quinlan">Ross Quinlan</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> used to generate a <a href="Decision_tree_learning" title="Decision tree learning">decision tree</a> from a dataset. ID3 is the precursor to the <a href="C4.5_algorithm" title="C4.5 algorithm">C4.5 algorithm</a>, and is typically used in the <a href="Machine_learning" title="Machine learning">machine learning</a> and <a href="Natural_language_processing" title="Natural language processing">natural language processing</a> domains.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>The ID3 algorithm begins with the original set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> as the <a href="Root_node" class="mw-redirect" title="Root node">root node</a>. On each <a href="Iteration" title="Iteration">iteration</a> of the algorithm, it iterates through every unused <a href="Feature_(machine_learning)" title="Feature (machine learning)">attribute</a> of the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> and calculates the <a href="Entropy_(information_theory)" title="Entropy (information theory)">entropy</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {H} {(S)}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} {(S)}}</annotation>

</semantics>

</math></span><img src="./2fbdd8a85ff3ceab57ac90d68f692638ccfafe29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.052ex; height:2.843ex;" alt="{\displaystyle \mathrm {H} {(S)}}" loading="lazy"></span> or the <a href="Information_gain_in_decision_trees" class="mw-redirect" title="Information gain in decision trees">information gain</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle IG(S)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle IG(S)}</annotation>

</semantics>

</math></span><img src="./193aeae84156415dc373c335244a790573513733.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.307ex; height:2.843ex;" alt="{\displaystyle IG(S)}" loading="lazy"></span> of that attribute. It then selects the attribute which has the smallest entropy (or largest information gain) value. The set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> is then split or <a href="Partition_of_a_set" title="Partition of a set">partitioned</a> by the selected attribute to produce subsets of the data. (For example, a node can be split into <a href="Child_node" class="mw-redirect" title="Child node">child nodes</a> based upon the subsets of the population whose ages are less than 50, between 50 and 100, and greater than 100.) The algorithm continues to <a href="Recursion_(computer_science)" title="Recursion (computer science)">recurse</a> on each subset, considering only attributes never selected before.

</p><p>Recursion on a subset may <a href="Base_case_(recursion)" class="mw-redirect" title="Base case (recursion)">stop</a> in one of these cases:

</p>

<ul><li>every element in the subset belongs to the same class; in which case the node is turned into a <a href="Leaf_node" class="mw-redirect" title="Leaf node">leaf node</a> and labelled with the class of the examples.</li>

<li>there are no more attributes to be selected, but the examples still do not belong to the same class. In this case, the node is made a leaf node and labelled with the <a href="Mode_(statistics)" title="Mode (statistics)">most common class</a> of the examples in the subset.</li>

<li>there are <a href="Empty_set" title="Empty set">no examples in the subset</a>, which happens when no example in the parent set was found to match a specific value of the selected attribute. An example could be the absence of a person among the <a href="Population_(statistics)" class="mw-redirect" title="Population (statistics)">population</a> with age over 100 years. Then a leaf node is created and labelled with the most common class of the examples in the parent node's set.</li></ul>

<p>Throughout the algorithm, the decision tree is constructed with each non-terminal node (<a href="Internal_node" class="mw-redirect" title="Internal node">internal node</a>) representing the selected <a href="Feature_(machine_learning)" title="Feature (machine learning)">attribute</a> on which the data was split, and terminal nodes (leaf nodes) representing the class label of the final subset of this branch.

</p>

<div class="mw-heading mw-heading3"><h3 id="Summary">Summary</h3></div>

<ol><li>Calculate the <a href="Entropy_(information_theory)" title="Entropy (information theory)">entropy</a> of every <a href="Feature_(machine_learning)" title="Feature (machine learning)">attribute</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> of the data set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span>.</li>

<li>Partition ("split") the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> into <a href="Subset" title="Subset">subsets</a> using the attribute for which the <a href="Posterior_distribution" class="mw-redirect" title="Posterior distribution">resulting</a> entropy after splitting is <a href="Minimum" class="mw-redirect" title="Minimum">minimized</a>; or, equivalently, information gain is <a href="Maximum" class="mw-redirect" title="Maximum">maximum</a>.</li>

<li>Make a decision tree <a href="Node_(computer_science)" title="Node (computer science)">node</a> containing that attribute.</li>

<li>Recurse on subsets using the remaining attributes.</li></ol>

<div class="mw-heading mw-heading3"><h3 id="Properties">Properties</h3></div>

<p>ID3 does not guarantee an optimal solution. It can converge upon <a href="Local_optimum" class="mw-redirect" title="Local optimum">local optima</a>. It uses a <a href="Greedy_algorithm" title="Greedy algorithm">greedy strategy</a> by selecting the locally best attribute to split the dataset on each iteration. The <a href="Algorithm's_optimality" class="mw-redirect" title="Algorithm's optimality">algorithm's optimality</a> can be improved by using <a href="Backtracking" title="Backtracking">backtracking</a> during the search for the optimal decision tree at the cost of possibly taking longer.

</p><p>ID3 can <a href="Overfitting" title="Overfitting">overfit</a> the training data. To avoid overfitting, smaller decision trees should be preferred over larger ones. This algorithm usually produces small trees, but it does not always produce the smallest possible decision tree.

</p><p>ID3 is harder to use on continuous data than on factored data (factored data has a discrete number of possible values, thus reducing the possible branch points). If the values of any given attribute are <a href="Continuous_variable" class="mw-redirect" title="Continuous variable">continuous</a>, then there are many more places to split the data on this attribute, and searching for the best value to split by can be time-consuming.

</p>

<div class="mw-heading mw-heading3"><h3 id="Usage">Usage</h3></div>

<p>The ID3 algorithm is used by training on a <a href="Data_set" title="Data set">data set</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> to produce a <a href="Decision_tree" title="Decision tree">decision tree</a> which is stored in <a href="Computer_memory" title="Computer memory">memory</a>. At <a href="Run_time_(program_lifecycle_phase)" class="mw-redirect" title="Run time (program lifecycle phase)">runtime</a>, this decision tree is used to <a href="Statistical_classification" title="Statistical classification">classify</a> new test cases (<a href="Feature_vector" class="mw-redirect" title="Feature vector">feature vectors</a>) by <a href="Tree_traversal" title="Tree traversal">traversing</a> the decision tree using the features of the datum to arrive at a leaf node.

</p>

<div class="mw-heading mw-heading2"><h2 id="The_ID3_metrics">The ID3 metrics</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Entropy">Entropy</h3></div>

<p><a href="Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {H} {(S)}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} {(S)}}</annotation>

</semantics>

</math></span><img src="./2fbdd8a85ff3ceab57ac90d68f692638ccfafe29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.052ex; height:2.843ex;" alt="{\displaystyle \mathrm {H} {(S)}}" loading="lazy"></span> is a measure of the amount of uncertainty in the (data) set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> (i.e. entropy characterizes the (data) set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span>).

</p>

</mrow>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}</annotation>

</semantics>

</math></span><img src="./67d6db8ff7b06b9545b541abc6a8cb3c09cea6b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:27.199ex; height:5.676ex;" alt="{\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}" loading="lazy"></span></dd></dl>

<p>Where,

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> – The <a href="Local_variable" title="Local variable">current dataset</a> for which entropy is being calculated

<ul><li>This changes at each step of the ID3 algorithm, either to a subset of the previous set in the case of splitting on an attribute or to a "sibling" partition of the parent in case the recursion terminated previously.</li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> – The set of classes in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(x)}</annotation>

</semantics>

</math></span><img src="./8cb7afced134ef75572e5314a5d278c2d644f438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.398ex; height:2.843ex;" alt="{\displaystyle p(x)}" loading="lazy"></span> – The <a href="Proportion_(mathematics)" title="Proportion (mathematics)">proportion</a> of the <a href="Cardinality" title="Cardinality">number of elements</a> in class <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> to the number of elements in set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span></li></ul>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} {(S)}=0}</annotation>

</semantics>

</math></span><img src="./41ab980e708b87f41a2ad7f222207bb0a4bdf29c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.313ex; height:2.843ex;" alt="{\displaystyle \mathrm {H} {(S)}=0}" loading="lazy"></span>, the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> is perfectly classified (i.e. all elements in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> are of the same class).

</p><p>In ID3, entropy is calculated for each remaining attribute. The attribute with the <b>smallest</b> entropy is used to split the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> on this iteration. Entropy in <a href="Information_theory" title="Information theory">information theory</a> measures how much information is <a href="Expected_value" title="Expected value">expected</a> to be gained upon <a href="Sampling_(signal_processing)" title="Sampling (signal processing)">measuring</a> a <a href="Random_variable" title="Random variable">random variable</a>; as such, it can also be used to quantify the amount to which the <a href="Probability_distribution" title="Probability distribution">distribution</a> of the quantity's values is unknown. A <a href="Constant_(mathematics)" title="Constant (mathematics)">constant</a> quantity has zero entropy, as its distribution is <a href="Complete_information" title="Complete information">perfectly known</a>. In contrast, a uniformly distributed random variable (<a href="Discrete_uniform_distribution" title="Discrete uniform distribution">discretely</a> or <a href="Continuous_uniform_distribution" title="Continuous uniform distribution">continuously</a> uniform) maximizes entropy. Therefore, the greater the entropy at a node, the less information is known about the classification of data at this stage of the tree; and therefore, the greater the potential to improve the classification here.

</p><p>As such, ID3 is a <a href="Greedy_algorithm" title="Greedy algorithm">greedy</a> <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a> performing a <a href="Best-first_search" title="Best-first search">best-first search</a> for <a href="Locally_optimal" class="mw-redirect" title="Locally optimal">locally optimal</a> entropy values. Its accuracy can be improved by preprocessing the data.

</p>

<div class="mw-heading mw-heading3"><h3 id="Information_gain">Information gain</h3></div>

<p><a href="Information_gain_in_decision_trees" class="mw-redirect" title="Information gain in decision trees">Information gain</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle IG(A)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle IG(A)}</annotation>

</semantics>

</math></span><img src="./9ec902c7663c979a577d09d641b684bcdd1988ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.551ex; height:2.843ex;" alt="{\displaystyle IG(A)}" loading="lazy"></span> is the measure of the difference in entropy from before to after the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> is split on an attribute <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>. In other words, how much uncertainty in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> was reduced after splitting set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> on attribute <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>.

</p>

</mrow>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}</annotation>

</semantics>

</math></span><img src="./b457b0e91764ddd152a362572fc0b6b9a5af3b82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:51.106ex; height:5.676ex;" alt="{\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}" loading="lazy"></span></dd></dl>

<p>Where,

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} (S)}</annotation>

</semantics>

</math></span><img src="./cd5a640edd6106bdf9765bd20ec11c87157beed0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.052ex; height:2.843ex;" alt="{\displaystyle \mathrm {H} (S)}" loading="lazy"></span> – Entropy of set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> – The subsets created from splitting set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> by attribute <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\bigcup _{t\in T}t}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\bigcup _{t\in T}t}</annotation>

</semantics>

</math></span><img src="./1a05cd6f1bdea81839cd38c775242f8ac7be1cb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:8.671ex; height:5.676ex;" alt="{\displaystyle S=\bigcup _{t\in T}t}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(t)}</annotation>

</semantics>

</math></span><img src="./9b827c545ca1487214f0c498131228ef87718ece.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:3.908ex; height:2.843ex;" alt="{\displaystyle p(t)}" loading="lazy"></span> – The proportion of the number of elements in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> to the number of elements in set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span></li>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {H} (t)}</annotation>

</semantics>

</math></span><img src="./ca49b2b2fd5a2702a69936065c941694788cebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.392ex; height:2.843ex;" alt="{\displaystyle \mathrm {H} (t)}" loading="lazy"></span> – Entropy of subset <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span></li></ul>

<p>In ID3, information gain can be calculated (instead of entropy) for each remaining attribute. The attribute with the <b>largest</b> information gain is used to split the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> on this iteration.

</p>

<ul><li><a href="Classification_and_regression_tree" class="mw-redirect" title="Classification and regression tree">Classification and regression tree</a> (CART)</li>

<li><a href="C4.5_algorithm" title="C4.5 algorithm">C4.5 algorithm</a></li>

<li><a href="Decision_tree_learning" title="Decision tree learning">Decision tree learning</a>

<ul><li><a href="Decision_tree_model" title="Decision tree model">Decision tree model</a></li></ul></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFTaggartDeSimoneShihFilloux2012" class="citation journal cs1">Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3465671">"Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo"</a>. <i>Nature Structural & Molecular Biology</i>. <b>19</b> (7): <span class="nowrap">719–</span>721. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fnsmb.2327">10.1038/nsmb.2327</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1545-9993">1545-9993</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3465671">3465671</a></span>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/22705790">22705790</a>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFMitchell1997" class="citation book cs1">Mitchell, Tom Michael (1997). <span class="id-lock-limited" title="Free access subject to limited trial, subscription normally required"><a rel="nofollow" class="external text" href="https://archive.org/details/machinelearning00mitc_087"><i>Machine Learning</i></a></span>. New York, NY: McGraw-Hill. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/machinelearning00mitc_087/page/n66">55</a>–58. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0070428077</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/36417892">36417892</a>.</cite></li>

<li><cite id="CITEREFGrzymala-Busse1993" class="citation journal cs1">Grzymala-Busse, Jerzy W. (February 1993). <a rel="nofollow" class="external text" href="https://people.eecs.ku.edu/~jerzygb/j24-sel.pdf">"Selected Algorithms of Machine Learning from Examples"</a> <span class="cs1-format">(PDF)</span>. <i>Fundamenta Informaticae</i>. <b>18</b> (2): <span class="nowrap">193–</span>207 – via ResearchGate.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Seminars – <a rel="nofollow" class="external text" href="http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html">http://www2.cs.uregina.ca/</a></li>

<li>Description and examples – <a rel="nofollow" class="external text" href="http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm">http://www.cise.ufl.edu/</a></li>

<li>Description and examples – <a rel="nofollow" class="external text" href="http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html">http://www.cis.temple.edu/</a></li>

<li><a rel="nofollow" class="external text" href="http://jeremykun.com/2012/10/08/decision-trees-and-political-party-classification/">Decision Trees and Political Party Classification</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-07-01" href="https://en.wikipedia.org/wiki/?title=ID3_algorithm&oldid=1232052944">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>